#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;

const int N = 1e6 + 10, INF = 0x3f3f3f3f;

int prim[N], R;
int p[N], sum[N];//p为i的最小质因子的约数和,sum为i的约数和
bool st[N];

void get_primes(int n)
{
    sum[1] = 1;
    for (int i = 2;i <= n;i++) {
        if (st[i] == 0) {
            prim[++R] = i;
            p[i] = sum[i] = i + 1;
        }
        for (int j = 1;prim[j] * i <= n;j++) {
            st[i * prim[j]] = 1;
            if (i % prim[j] == 0) {
                p[i * prim[j]] = p[i] * prim[j] + 1;
                sum[i * prim[j]] = sum[i] / p[i] * (p[i] * prim[j] + 1);
                break;
            } else {
                p[i * prim[j]] = prim[j] + 1;
                sum[i * prim[j]] = sum[i] * (prim[j] + 1);
            }
        }
    }
}